In modern simulated environments a user may connect with other users in numerous different ways depending on the connection architecture of the environment. The most common connection architectures in modern simulations are the server-client model and the peer to peer model.
Both of the models have their respective benefits and drawbacks. The server-client model requires special infrastructure to allow user connections. This infrastructure requires constant upkeep and is costly to develop and maintain. The peer to peer model presents an alternative to the server-client model. The peer to peer model does not require the additional costly infrastructure of the server client-model to allow user connections although some infrastructure may be needed to initially create the connections. Unlike the server-client model the peer to peer model is limited to deterministic simulation because each peer is synchronized individually with no master controlling the overall behavior of the simulation on each client. The peer to peer model also presents difficulty in connecting and maintaining connections between peers. Particularly problematic for the peer to peer model is the process by which peers connect to each other, referred to as Network Address Translation (NAT) punch through.
NAT is an Internet standard that enables a local area network (LAN) to use of one set of private IP addresses for internal traffic and a second set of global IP addresses for external traffic. A node that has NAT capability is often referred as “NAT box.” Though IPv6 has introduced a larger global IP address set for connection to the internet the amount of users connecting to the internet through IPv4 and NAT-enabled routers continues remain high with some internet providers even creating networks where more than one NAT must be traversed to access the global internet.
A NAT (literally) translates network (IP) address between the two networks. Network Address Port Translation (NAPT) translates not only IP address but also port numbers of a transport layer protocol. Although NAT/NAPT has its good properties, there is a significant side effect. If the translation is dynamically performed, nodes in the external network have no way to know the IP address (and the port number) on the NAT ahead of time to reach a node in the internal network. Unfortunately, this is the most common behavior of NAT in the residential and SOHO routers deployed in the current market.
NAPT (hereinafter, called “NAT” unless stated otherwise) is the most common NAT in today's residential routers. In a NAT, an IP address is used to identify an end node, or a host. There may be more than one application running on the same node. Typically, each application has a unique port number allocated to the same IP address. That is, in order to identify an application, both an IP address and a port number must be specified.
The notion of “port” is important to understand NAT behavior. A NAT allows two or more IP nodes behind the NAT to share a single global IP address, by translating the port numbers. When an application on a node sends a packet to a server on the public network, the NAT allocates a public transport address, having an external IP address and an external port number that is associated with the source transport address. This association created by NAT is known as “NAT Binding”. When another application on a different node behind the NAT sends a packet to the same server the NAT creates another binding with the same external IP address but with another port number. For the server, those packets look like they originated from the same node but from different port numbers. The server then simply sends responses back to those external transport addresses on the NAT. Since the NAT already has bindings for packets received from the server these packets can be correctly forwarded to the associated local nodes. A problem occurs when a node behind the NAT wants to be accessed from anyone from the public network. A NAT binding cannot be created by packets from the pubic network. The NAT can forward the inbound packets only if an associated binding already exists.
To address this problem, many routers have a Port Forwarding feature which allows a user to manually configure the routing table in the router. As opposed to NAT binding, a specified external transport address on the NAT is static so that any inbound packets arrived on the external transport address are forwarded to the specified local node on the private network. Unfortunately, such manual configuration requires users to have sufficient knowledge of TCP/IP protocol and NAT. Users also need to know the transport addresses of the applications running on the local nodes to configure the port forwarding tables. Since port forwarding is not a standardized feature, each router has a different configuration menu some of which might not be able to meet requirements from an application. To application vendors, the cost for customer support for those users who are experiencing trouble with configuration for various NATs would be very significant.
It has been observed that NAT treatment of User Datagram Protocol (UDP) varies among implementations. Four treatments commonly observed in implementations are, Full Cone, Restricted Cone, Port Restricted Cone and Symmetric. A full cone NAT is one where all requests from the same internal IP address and port are mapped to the same external IP address and port. Furthermore, any external host can send a packet to the internal host, by sending a packet to the mapped external address. In a restricted cone NAT all requests from the same internal IP address and port are mapped to the same external IP address and port. Unlike a full cone NAT, an external host (with IP address X) can send a packet to the internal host only if the internal host had previously sent a packet to IP address X. A port restricted cone NAT is like a restricted cone NAT, but the restriction includes port numbers. Specifically, an external host can send a packet, with source IP address X and source port P, to the internal host only if the internal host had previously sent a packet to IP address X and port P.
In a symmetric NAT all requests from the same internal IP address and port, to a specific destination IP address and port, are mapped to the same external IP address and port. If the same host sends a packet with the same source address and port, but to a different destination, a different mapping is used. Furthermore, only the external host that receives a packet can send a UDP packet back to the internal host.
Similar to a restricted cone NAT a stateful firewall limits the packets allowed to be sent to the host to addresses that the host has already sent to. This firewall type can present difficulty in peer to peer connections similar to those presented by a NAT.
One prior art NAT traversal solution has been developed based on UPnP (Universal Plug and Play), a technical specification that enables communications among home appliances such as PC, Audio/Video devices, phones and etc., proposed by Microsoft in 1999 and supported by more than 20 companies including Intel, 3Com, AT&T, Dell Computer, etc. UPnP provides NAT traversal solution that allows a node behind a UPnP compliant NAT to discover the presence of the NAT and to add and delete external port mapping on the NAT. It is an automatic port forwarding configuration, so to speak. Many residential routers support UPnP today, however, not all of them do. Some UPnP compliant routers have UPnP mode turned off by default. Users may be prompted to turn on the UPnP mode manually, but this essentially falls into the same issue with the port forwarding.
A major problem with NAT traversal in the current peer to peer networking environment is that there is no standardized NAT behavior common to all types of routers and user side solutions for NAT traversal have been developed but have not been implemented completely. Features such as UPnP and Port Forwarding are available on some but not all consumer grade routers. These features can enhance connectivity between peers making connections easier and more reliable.
Generally matchmaking over a network peers are chosen based on easily collected information about the user such as win rate, user rank, download rating, community rating etc. A difficulty specific to peer to peer network matchmaking is that a user may not be able to use the network or the desired network application until all of the peers have connected with each other. Peer to Peer networks are especially susceptible to users with bad network connections because if one peer takes particularly long to join the match all of the other peers must wait until that peer has joined before being allowed to use the application and if one user drops from the application allowing another user to join while the network is established may be very complex or not possible. Thus there is a need in the art for a way for matchmaking to account for NAT and firewall differences between peers during peer selection to enhance the user experience and provide better connectivity.